package qjc.g_链表;

import com.链表.练习题.ListNode;

public class g6_合并两个有序链表 {
    /**
     * 创建一个虚拟头节点，方便操作，初始化指针 p，指向虚拟头节点，
     * 遍历两个链表，直到其中一个链表为空，如果 list1 的当前节点值小于 list2 的当前节点值，
     * 否则，将 list2 的当前节点接到 p 的后面，如果 list1 不为空，
     * 将 list1 的剩余部分接到 p 的后面，如果 list2 不为空，将 list2 的剩余部分接到 p 的后面
     * 返回合并后的链表头节点（虚拟头节点的下一个节点）
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode s = new ListNode(-1,null);
        ListNode p = s;
        while (list1 != null && list2 != null){
            if(list1.val < list2.val){
                p.next = list1;
                list1 = list1.next;
            }else {
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }
        if(list1 != null){
            p.next = list1;
        }
        if(list2 != null){
            p.next = list2;
        }
        return s.next;
    }
}
